home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / kernel / ofs / ofsAlloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-19  |  62.8 KB  |  2,179 lines
  1. /* 
  2.  * ofsAlloc.c --
  3.  *
  4.  *    Block and fragment allocation and truncation.  This code is specific
  5.  *    to 4Kbyte blocks with 1Kbyte fragments.
  6.  *
  7.  * Copyright 1987 Regents of the University of California
  8.  * All rights reserved.
  9.  * Permission to use, copy, modify, and distribute this
  10.  * software and its documentation for any purpose and without
  11.  * fee is hereby granted, provided that the above copyright
  12.  * notice appear in all copies.  The University of California
  13.  * makes no representations about the suitability of this
  14.  * software for any purpose.  It is provided "as is" without
  15.  * express or implied warranty.
  16.  */
  17.  
  18. #ifndef lint
  19. static char rcsid[] = "$Header: /cdrom/src/kernel/Cvsroot/kernel/ofs/ofsAlloc.c,v 9.17 92/07/31 14:16:02 mgbaker Exp $ SPRITE (Berkeley)";
  20. #endif not lint
  21.  
  22. #include <sprite.h>
  23. #include <fs.h>
  24. #include <fsutil.h>
  25. #include <fscache.h>
  26. #include <fslcl.h>
  27. #include <fsNameOps.h>
  28. #include <fsio.h>
  29. #include <spriteTime.h>
  30. #include <devFsOpTable.h>
  31. #include <fsStat.h>
  32. #include <timer.h>
  33. #include <rpc.h>
  34. #include <proc.h>
  35. #include <string.h>
  36. #include <fsdm.h>
  37. #include <ofs.h>
  38.  
  39. #include <stdio.h>
  40.  
  41. /*
  42.  * Each domain, which is a separate piece of disk, is locked
  43.  * during allocation.
  44.  */
  45. #define LOCKPTR (&ofsPtr->dataBlockLock)
  46.  
  47. /*
  48.  * A table indexed by a 4 bit value is used by the allocation routine to 
  49.  * quickly determine the location of 1, 2, and 3K fragments in a byte.  
  50.  * The indices of the fragments start from 0.  If there is no such fragment in 
  51.  * the byte then a -1 is used.
  52.  */
  53.  
  54. static int fragTable[16][OFS_NUM_FRAG_SIZES] = {
  55. /* 0000 */ {-1, -1, -1},
  56. /* 0001 */ {-1, -1, 0},
  57. /* 0010 */ {3, 0, -1},
  58. /* 0011 */ {-1, 0, -1},
  59. /* 0100 */ {0, 2, -1},
  60. /* 0101 */ {0, -1, -1},
  61. /* 0110 */ {0, -1, -1},
  62. /* 0111 */ {0, -1, -1},
  63. /* 1000 */ {-1, -1, 1},
  64. /* 1001 */ {-1, 1, -1},
  65. /* 1010 */ {1, -1, -1},
  66. /* 1011 */ {1, -1, -1},
  67. /* 1100 */ {-1, 2, -1},
  68. /* 1101 */ {2, -1, -1},
  69. /* 1110 */ {3, -1, -1},
  70. /* 1111 */ {-1, -1, -1}
  71. };
  72.  
  73. /*
  74.  * Array to provide the ability to set and extract bits out of a bitmap byte.
  75.  */
  76.  
  77. static unsigned char bitMasks[8] = {0x80, 0x40, 0x20, 0x10, 0x8, 0x4, 0x2, 0x1};
  78.  
  79. /*
  80.  * Macros to get to the 4-bit fragment masks of the two 4K blocks that are 
  81.  * stored in a byte.
  82.  */
  83.  
  84. #define    UpperBlockFree(byte)    (((byte) & 0xf0) == 0x00)
  85. #define    LowerBlockFree(byte)    (((byte) & 0x0f) == 0x00)
  86. #define    BothBlocksFree(byte)    (((byte) & 0xff) == 0x00)
  87. #define    GetUpperFragMask(byte) (((byte) >> 4) & 0x0f)
  88. #define    GetLowerFragMask(byte) ((byte) & 0x0f)
  89.  
  90. /*
  91.  * Macro to get a pointer into the bit map for a particular block.
  92.  */
  93.  
  94. #define    BlockToCylinder(ofsPtr, blockNum) \
  95.  (unsigned int) (blockNum) / (ofsPtr)->headerPtr->geometry.blocksPerCylinder
  96.  
  97. #define    GetBitmapPtr(ofsPtr, blockNum) \
  98.     &((ofsPtr)->dataBlockBitmap[BlockToCylinder(ofsPtr, blockNum) * \
  99.           (ofsPtr)->bytesPerCylinder + \
  100.           ((unsigned int) ((blockNum) % \
  101.           (ofsPtr)->headerPtr->geometry.blocksPerCylinder) / 2)])
  102.  
  103. #define    LAST_FRAG     (FS_FRAGMENTS_PER_BLOCK - 1)
  104. #define    FRAG_OFFSET_MASK (FS_FRAGMENTS_PER_BLOCK - 1)
  105.  
  106. /*
  107.  * Size of a fragment (1K).
  108.  */
  109. #define FRAG_SIZE (FS_BLOCK_SIZE / FS_FRAGMENTS_PER_BLOCK)
  110.  
  111. /*
  112.  * Percent of disk to keep free.
  113.  */
  114. int    ofsPercentFree = 10;
  115.  
  116. /*
  117.  * Block allocation style (settable with FS_SET_ALLOC_GAP Fs_Command)
  118.  *    CONTIGUOUS    Blocks are allocated coniguously, beginning at the
  119.  *            beginning of the cylinder.
  120.  *    SKIP_ONE    Blocks are allocated with one free block between
  121.  *            each allocated block.  The extra block gives the
  122.  *            software time to generate a new disk request
  123.  *            before the next allocated block rotates past the head.
  124.  */
  125. #define CONTIGUOUS    0
  126. #define SKIP_ONE    1
  127.  
  128. int ofs_AllocGap = CONTIGUOUS;
  129.  
  130. /*
  131.  * Forward references.
  132.  */
  133. static void FindBlockInt _ARGS_((int hashSeed, Ofs_Domain *ofsPtr,
  134.         int nearBlock, Boolean allocate, int *blockNumPtr, 
  135.         unsigned char **bitmapPtrPtr));
  136. static ReturnStatus UpgradeFragment _ARGS_((Ofs_Domain *ofsPtr, 
  137.         Fsio_FileIOHandle *handlePtr, OfsBlockIndexInfo *indexInfoPtr,
  138.         int curLastBlock, int newLastFrag, Boolean dontWriteThru, 
  139.         int dontBlock, Boolean *dirtiedIndexPtr));
  140. static ReturnStatus AllocateBlock _ARGS_((Fsio_FileIOHandle *handlePtr, 
  141.         Fsdm_FileDescriptor *descPtr, OfsBlockIndexInfo *indexInfoPtr,
  142.         int newLastByte, int curLastBlock, int dontBlock,
  143.         Boolean *dirtiedIndexPtr));
  144. static ReturnStatus FragToBlock _ARGS_((Ofs_Domain *ofsPtr, 
  145.         Fsio_FileIOHandle *handlePtr, int blockNum, int dontBlock));
  146. static void PutInBadBlockFile _ARGS_((Fsio_FileIOHandle *handlePtr, 
  147.         Ofs_Domain *ofsPtr, int blockNum));
  148.  
  149.  
  150. /*
  151.  *----------------------------------------------------------------------
  152.  *
  153.  * OfsBlockAllocInit() --
  154.  *
  155.  *    Initialize the data structure needed for block allocation for the
  156.  *    given domain on a local disk.
  157.  *
  158.  * Results:
  159.  *    None.
  160.  *
  161.  * Side effects:
  162.  *    Memory is allocated for the bit map, the cylinder map and the fragment
  163.  *    lists.  The bit map is read in and the cylinder map and fragment lists 
  164.  *    are initialized.
  165.  *
  166.  *----------------------------------------------------------------------
  167.  */
  168. ReturnStatus
  169. OfsBlockAllocInit(ofsPtr)
  170.     register    Ofs_Domain    *ofsPtr;    /* Domain to initialize block
  171.                          * allocation for. */
  172. {
  173.     int                blocksPerCylinder;
  174.     int                bitmapBytes;
  175.     register    unsigned char     *bitmapPtr;
  176.     register    OfsCylinder    *cylinderPtr;
  177.     register    OfsFragment    *fragPtr;
  178.     register    int        i;
  179.     register    int        j;
  180.     register    int        k;
  181.     int                *fragOffsetPtr;
  182.     ReturnStatus        status;
  183.  
  184.     Sync_LockInitDynamic(&(ofsPtr->dataBlockLock), "Fs:ofsDataBlockLock");
  185.     /*
  186.      * Ensure some free disk space for disk block allocation.
  187.      */
  188.     ofsPtr->minKFree =
  189.     (ofsPtr->headerPtr->dataBlocks * FS_FRAGMENTS_PER_BLOCK) /
  190.                 ofsPercentFree;
  191.  
  192.     blocksPerCylinder = ofsPtr->headerPtr->geometry.blocksPerCylinder;
  193.  
  194.     /*
  195.      * Allocate the bit map.
  196.      */
  197.     bitmapBytes = (unsigned int) (blocksPerCylinder + 1) / 2;
  198.     ofsPtr->bytesPerCylinder = bitmapBytes;
  199.     ofsPtr->dataBlockBitmap = (unsigned char *) 
  200.     malloc(ofsPtr->headerPtr->bitmapBlocks * FS_BLOCK_SIZE);
  201.  
  202.     /* 
  203.      * Read in the bit map.  The Block I/O interface is based on 1K blocks,
  204.      * but the header information is in terms of 4K blocks.
  205.      */
  206.     status = OfsDeviceBlockIO(ofsPtr, FS_READ, 
  207.         ofsPtr->headerPtr->bitmapOffset * 4, 
  208.         ofsPtr->headerPtr->bitmapBlocks * 4,
  209.         (Address) ofsPtr->dataBlockBitmap);
  210.     if (status != SUCCESS) {
  211.     printf(
  212.         "OfsBlockAllocInit: Could not read data block bitmap.\n");
  213.     return(status);
  214.     }
  215.  
  216.     /*
  217.      * Initialize the 3 fragment lists (1K, 2K and 3K).
  218.      */
  219.     for (i = 0; i < OFS_NUM_FRAG_SIZES; i++) {
  220.     ofsPtr->fragLists[i] = (List_Links *) malloc(sizeof(List_Links));
  221.     List_Init(ofsPtr->fragLists[i]);
  222.     }
  223.  
  224.     /*
  225.      * Allocate an array cylinder information.
  226.      */
  227.     ofsPtr->cylinders = (OfsCylinder *) 
  228.     malloc(sizeof(OfsCylinder) * ofsPtr->headerPtr->dataCylinders);
  229.  
  230.     /*
  231.      * Now go through the bit map finding all of the fragments and putting
  232.      * them onto the appropriate lists.  Also determine cylinder information.
  233.      */
  234.     bitmapPtr = ofsPtr->dataBlockBitmap;
  235.     cylinderPtr = ofsPtr->cylinders;
  236.     for (i = 0; i < ofsPtr->headerPtr->dataCylinders; i++, cylinderPtr++) {
  237.     cylinderPtr->blocksFree = 0;
  238.     for (j = 0; j < bitmapBytes; j++, bitmapPtr++) {
  239.         if (UpperBlockFree(*bitmapPtr)) {
  240.         cylinderPtr->blocksFree++;
  241.         } else {
  242.         fragOffsetPtr = fragTable[GetUpperFragMask(*bitmapPtr)];
  243.         for (k = 0; k < OFS_NUM_FRAG_SIZES; k++, fragOffsetPtr++) {
  244.             if (*fragOffsetPtr != -1) {
  245.             fragPtr = (OfsFragment *) malloc(sizeof(OfsFragment));
  246.             List_Insert((List_Links *) fragPtr, 
  247.                     LIST_ATREAR(ofsPtr->fragLists[k]));
  248.             fragPtr->blockNum = i * blocksPerCylinder + j * 2;
  249.             }
  250.         }
  251.         }
  252.  
  253.         /*
  254.          * There may be an odd number of blocks per cylinder.  If so
  255.          * and are at the end of the bit map for this cylinder, then
  256.          * we can bail out now.
  257.          */
  258.  
  259.         if (j == (bitmapBytes - 1) && (blocksPerCylinder & 0x1)) {
  260.         continue;
  261.         }
  262.  
  263.         if (LowerBlockFree(*bitmapPtr)) {
  264.         cylinderPtr->blocksFree++;
  265.         } else {
  266.         fragOffsetPtr = fragTable[GetLowerFragMask(*bitmapPtr)];
  267.         for (k = 0; k < OFS_NUM_FRAG_SIZES; k++, fragOffsetPtr++) {
  268.             if (*fragOffsetPtr != -1) {
  269.             fragPtr = (OfsFragment *) malloc(sizeof(OfsFragment));
  270.             List_Insert((List_Links *) fragPtr, 
  271.                     LIST_ATREAR(ofsPtr->fragLists[k]));
  272.             fragPtr->blockNum = i * blocksPerCylinder + j * 2 + 1;
  273.             }
  274.         }
  275.         }
  276.     }
  277.     }
  278.  
  279.     return(SUCCESS);
  280. }
  281.  
  282. /*
  283.  *----------------------------------------------------------------------
  284.  *
  285.  * Ofs_BlockAllocate --
  286.  *
  287.  *    Allocate disk space for the given file.  This routine only allocates
  288.  *    one block beginning at offset and going for numBytes.   If 
  289.  *    offset + numBytes crosses a block boundary then a panic will occur.
  290.  *
  291.  * Results:
  292.  *    None.
  293.  *
  294.  * Side effects:
  295.  *    The file descriptor is modified to contain pointers to the allocated
  296.  *    blocks.  Also *blockAddrPtr is set to the block that was allocated.
  297.  *
  298.  *----------------------------------------------------------------------
  299.  */
  300. ReturnStatus
  301. Ofs_BlockAllocate(domainPtr, handlePtr, offset, numBytes, flags, blockAddrPtr,
  302.         newBlockPtr)
  303.     Fsdm_Domain        *domainPtr;    /* Domain of file. */
  304.     register Fsio_FileIOHandle *handlePtr;    /* Local file handle. */
  305.     int         offset;        /* Offset to allocate at. */
  306.     int         numBytes;    /* Number of bytes to allocate. */
  307.     int            flags;        /* FSCACHE_DONT_BLOCK */
  308.     int            *blockAddrPtr;     /* Disk address of block allocated. */
  309.     Boolean        *newBlockPtr;    /* TRUE if there was no block allocated
  310.                      * before. */
  311. {
  312.     Ofs_Domain            *ofsPtr = OFS_PTR_FROM_DOMAIN(domainPtr);
  313.     register Fsdm_FileDescriptor    *descPtr;
  314.     register int        blockNum;
  315.     OfsBlockIndexInfo        indexInfo;
  316.     int                newLastByte;
  317.     int                curLastBlock;
  318.     int                curLastFrag;
  319.     Boolean            dirtiedIndex = FALSE;
  320.     ReturnStatus        status;
  321.  
  322.     descPtr = handlePtr->descPtr;
  323.  
  324.     *blockAddrPtr = FSDM_NIL_INDEX;
  325.     newLastByte = offset + numBytes - 1;
  326.     blockNum = (unsigned int) offset / FS_BLOCK_SIZE;
  327.  
  328.     if ((unsigned int) (newLastByte) / FS_BLOCK_SIZE != blockNum) {
  329.     panic("OfsFileAllocate: Trying to allocate more than one block\n");
  330.     }
  331.  
  332.     if (descPtr->lastByte != -1) {
  333.     curLastBlock = (unsigned int) (descPtr->lastByte) / FS_BLOCK_SIZE;
  334.     } else {
  335.     curLastBlock = -1;
  336.     }
  337.  
  338.     /*
  339.      * If are allocating past the current last block in the file, then
  340.      * make the last block into a full block.
  341.      */
  342.     if (curLastBlock != -1 && curLastBlock < FSDM_NUM_DIRECT_BLOCKS &&
  343.         blockNum > curLastBlock) {
  344.     curLastFrag = (unsigned int) (descPtr->lastByte & FS_BLOCK_OFFSET_MASK)
  345.                 / FS_FRAGMENT_SIZE;
  346.     if (curLastFrag < LAST_FRAG) {
  347.         /*
  348.          * Upgrade the fragment to a full block.
  349.          */
  350.         status = FragToBlock(ofsPtr, handlePtr, curLastBlock, flags);
  351.         if (status != SUCCESS) {
  352.         return(status);
  353.         }
  354.     }
  355.     }
  356.  
  357.     /*
  358.      * Set up the indexing structure here.
  359.      */
  360.     if (blockNum == 0) {
  361.     /*
  362.      * This is the first block of the file so there is no previous
  363.      * block.
  364.      */
  365.     status = OfsGetFirstIndex(ofsPtr, handlePtr, blockNum, &indexInfo,
  366.                  OFS_ALLOC_INDIRECT_BLOCKS);
  367.     if (status != SUCCESS) {
  368.         return(status);
  369.     }
  370.     } else {
  371.     /*
  372.      * This is not the first block in the file, so determine the
  373.      * previous block and then go to the first block.
  374.      */
  375.     status = OfsGetFirstIndex(ofsPtr, handlePtr, blockNum - 1, &indexInfo,
  376.                  OFS_ALLOC_INDIRECT_BLOCKS);
  377.     if (status != SUCCESS) {
  378.         return(status);
  379.     }
  380.     status = OfsGetNextIndex(handlePtr, &indexInfo, FALSE);
  381.     if (status != SUCCESS) {
  382.         OfsEndIndex(handlePtr, &indexInfo, FALSE);
  383.         return(status);
  384.     }
  385.     }
  386.  
  387.     *newBlockPtr = (*indexInfo.blockAddrPtr == FSDM_NIL_INDEX);
  388.  
  389.     /*
  390.      * Allocate space for the block, but only if we need to.  We don't need to
  391.      * call AllocateBlock if we're not adding a new block to the end of the
  392.      * file, and we're not adding a new fragment because the block is an
  393.      * indirect block (which we don't fragment).
  394.      */
  395.     if (!(curLastBlock == blockNum && blockNum >= FSDM_NUM_DIRECT_BLOCKS)) {
  396.     status = AllocateBlock(handlePtr, descPtr, &indexInfo, newLastByte, 
  397.                curLastBlock, flags, &dirtiedIndex);
  398.     }
  399.  
  400.     if (status == SUCCESS) {
  401.     *blockAddrPtr = *indexInfo.blockAddrPtr;
  402.     }
  403.  
  404.     OfsEndIndex(handlePtr, &indexInfo, dirtiedIndex);
  405.  
  406.     if (status != SUCCESS) {
  407.     return(status);
  408.     }
  409.     /*
  410.      * Update the size of the file.  A firstByte of 0 is used in
  411.      * named pipes to note that there is data in the pipe.
  412.      * NOTE:  We can almost check the stream flags FS_CONSUME here,
  413.      * except that when remote clients flush back named pipe blocks
  414.      * they clear that flag so we the server treat it like a regular
  415.      * file and don't consume or append.  Hence the check against fileType.
  416.      */
  417.  
  418.     if (newLastByte > descPtr->lastByte) {
  419.     descPtr->lastByte = newLastByte;
  420.     }
  421.     if (descPtr->firstByte == -1 && 
  422.     ((descPtr->fileType == FS_NAMED_PIPE) ||
  423.      (descPtr->fileType == FS_PSEUDO_DEV) ||
  424.      (descPtr->fileType == FS_XTRA_FILE))) {
  425.     descPtr->firstByte = 0;
  426.     }
  427.     descPtr->descModifyTime = Fsutil_TimeInSeconds();
  428.     descPtr->flags |= (FSDM_FD_INDEX_DIRTY|FSDM_FD_SIZE_DIRTY);
  429.     return(SUCCESS);
  430. }
  431.  
  432.  
  433. /*
  434.  *----------------------------------------------------------------------
  435.  *
  436.  * Ofs_FileTrunc --
  437.  *
  438.  *    Shorten a file to length bytes.  This updates the descriptor
  439.  *    and may free blocks and indirect blocks from the end of the file.
  440.  *
  441.  * Results:
  442.  *    Error if had problem with indirect blocks, otherwise SUCCESS.
  443.  *
  444.  * Side effects:
  445.  *    Any allocated blocks after the given size are deleted.
  446.  *
  447.  *----------------------------------------------------------------------
  448.  */
  449. /*ARGSUSED*/
  450. ReturnStatus
  451. Ofs_FileTrunc(domainPtr, handlePtr, size, delete)
  452.     Fsdm_Domain        *domainPtr;
  453.     Fsio_FileIOHandle    *handlePtr;    /* File to truncate. */
  454.     int            size;        /* Size to truncate the file to. */
  455.     Boolean        delete;        /* TRUE if Truncate for delete. */
  456. {
  457.     register Ofs_Domain     *ofsPtr = OFS_PTR_FROM_DOMAIN(domainPtr);
  458.     register Fsdm_FileDescriptor     *descPtr;
  459.     int                firstBlock;
  460.     int                firstFrag = 0;
  461.     int                lastBlock;
  462.     int                lastFrag;
  463.     ReturnStatus        status = SUCCESS;
  464.     OfsBlockIndexInfo        indexInfo;
  465.     int                newLastByte;
  466.     int                savedLastByte;
  467.     int                flags;
  468.     Boolean            dirty = FALSE;
  469.     int                fragsToFree;
  470.  
  471.     descPtr = handlePtr->descPtr;
  472.  
  473.     savedLastByte = descPtr->lastByte;
  474.  
  475.     newLastByte = size - 1;
  476.     if (descPtr->lastByte <= newLastByte) {
  477.     status = SUCCESS;
  478.     goto exit;
  479.     }
  480.  
  481.     /*
  482.      * Determine the first block and number of fragments in the first block.
  483.      * This is called from the pipe trunc routine if its length is zero,
  484.      * hence the check against firstByte here.
  485.      */
  486.  
  487.     if (descPtr->firstByte >= 0) {
  488.     firstBlock = (unsigned int) descPtr->firstByte / FS_BLOCK_SIZE;
  489.     } else if (newLastByte == -1) {
  490.     firstBlock = 0;
  491.     } else {
  492.     firstBlock = (unsigned int) newLastByte / FS_BLOCK_SIZE;
  493.     firstFrag = (unsigned int) (newLastByte & FS_BLOCK_OFFSET_MASK) / 
  494.                     FS_FRAGMENT_SIZE;
  495.     }
  496.  
  497.     /*
  498.      * Determine the last block and the number of fragments in it.
  499.      */
  500.  
  501.     lastBlock = (unsigned int) descPtr->lastByte / FS_BLOCK_SIZE;
  502.     if (lastBlock >= FSDM_NUM_DIRECT_BLOCKS) {
  503.     lastFrag = LAST_FRAG;
  504.     } else {
  505.     lastFrag = (descPtr->lastByte & FS_BLOCK_OFFSET_MASK)/FS_FRAGMENT_SIZE;
  506.     }
  507.  
  508.     /*
  509.      * Determine if the file is already short enough in terms of blocks.
  510.      */
  511.  
  512.     if (newLastByte != -1 && firstBlock == lastBlock && 
  513.     (lastFrag <= firstFrag || firstBlock >= FSDM_NUM_DIRECT_BLOCKS)) {
  514.     if (newLastByte < descPtr->lastByte) {
  515.         descPtr->lastByte = newLastByte;
  516.         descPtr->descModifyTime = Fsutil_TimeInSeconds();
  517.         descPtr->flags |= FSDM_FD_SIZE_DIRTY;
  518.     }
  519.     status = SUCCESS;
  520.     goto exit;
  521.     }
  522.  
  523.     flags = OFS_DELETE_INDIRECT_BLOCKS;
  524.     if (newLastByte == -1) {
  525.     flags |= OFS_DELETE_EVERYTHING;
  526.     }
  527.  
  528.     /*
  529.      * Loop through the blocks deleting them.
  530.      */
  531.     status = OfsGetFirstIndex(ofsPtr, handlePtr, firstBlock, &indexInfo, flags);
  532.     if (status != SUCCESS) {
  533.     printf( "Ofs_FileTrunc: Status %x setting up index\n",
  534.           status);
  535.     goto exit;
  536.     }
  537.     while (TRUE) {
  538.     if (indexInfo.blockAddrPtr == (int *) NIL ||
  539.         *indexInfo.blockAddrPtr == FSDM_NIL_INDEX) {
  540.         goto nextBlock;
  541.     }
  542.  
  543.     dirty = FALSE;
  544.  
  545.     if (newLastByte == -1) {
  546.         /*
  547.          * The file is being made empty.
  548.          */
  549.         if (indexInfo.blockNum == lastBlock && lastFrag < LAST_FRAG) {
  550.         OfsFragFree(ofsPtr, lastFrag + 1, 
  551.             (int) (*indexInfo.blockAddrPtr / FS_FRAGMENTS_PER_BLOCK),
  552.             *indexInfo.blockAddrPtr & FRAG_OFFSET_MASK);
  553.         descPtr->numKbytes -= lastFrag + 1;
  554.         } else {
  555.         OfsBlockFree(ofsPtr, 
  556.             (int) (*indexInfo.blockAddrPtr / FS_FRAGMENTS_PER_BLOCK));
  557.         descPtr->numKbytes -= FS_FRAGMENTS_PER_BLOCK;
  558.         }
  559.         *indexInfo.blockAddrPtr = FSDM_NIL_INDEX;
  560.     } else if (indexInfo.blockNum == firstBlock) {
  561.         /*
  562.          * The first block that we truncate becomes the last block in
  563.          * the file.  If we are still in direct blocks we have to
  564.          * chop this (new last block) into the right number of fragments.
  565.          */
  566.         if (firstBlock >= FSDM_NUM_DIRECT_BLOCKS) {
  567.         goto nextBlock;
  568.         }
  569.         if (firstBlock != lastBlock) {
  570.         fragsToFree = LAST_FRAG - firstFrag;
  571.         } else {
  572.         fragsToFree = lastFrag - firstFrag;
  573.         }
  574.         if (fragsToFree > 0) {
  575.         OfsFragFree(ofsPtr, fragsToFree,
  576.               (int) (*indexInfo.blockAddrPtr / FS_FRAGMENTS_PER_BLOCK),
  577.                 (*indexInfo.blockAddrPtr & FRAG_OFFSET_MASK)
  578.                  + firstFrag + 1);
  579.         descPtr->numKbytes -= fragsToFree;
  580.         }
  581.     } else if (indexInfo.blockNum >= FSDM_NUM_DIRECT_BLOCKS || 
  582.                indexInfo.blockNum < lastBlock || lastFrag == LAST_FRAG) {
  583.         /*
  584.          * This is a full block so delete it.
  585.          */
  586.         OfsBlockFree(ofsPtr, 
  587.          (int) (*indexInfo.blockAddrPtr / FS_FRAGMENTS_PER_BLOCK));
  588.         descPtr->numKbytes -= FS_FRAGMENTS_PER_BLOCK;
  589.         *indexInfo.blockAddrPtr = FSDM_NIL_INDEX;
  590.     } else {
  591.         /*
  592.          * Delete a fragment.  Only get here if are on the last block in 
  593.          * the file.
  594.          */
  595.         OfsFragFree(ofsPtr, lastFrag + 1, 
  596.           (int) (*indexInfo.blockAddrPtr / FS_FRAGMENTS_PER_BLOCK),
  597.             *indexInfo.blockAddrPtr & FRAG_OFFSET_MASK);
  598.         descPtr->numKbytes -= lastFrag + 1;
  599.         *indexInfo.blockAddrPtr = FSDM_NIL_INDEX;
  600.     }
  601.  
  602.     dirty = TRUE;
  603.  
  604. nextBlock:
  605.  
  606.     if (indexInfo.blockNum == lastBlock) {
  607.         break;
  608.     }
  609.  
  610.     status = OfsGetNextIndex(handlePtr, &indexInfo, dirty);
  611.     if (status != SUCCESS) {
  612.         printf( "Ofs_FileTrunc: Could not truncate file.\n");
  613.         OfsEndIndex(handlePtr, &indexInfo, FALSE);
  614.         goto exit;
  615.     }
  616.     }
  617.  
  618.     OfsEndIndex(handlePtr, &indexInfo, dirty);
  619.  
  620.     descPtr->lastByte = newLastByte;
  621.     descPtr->descModifyTime = Fsutil_TimeInSeconds();
  622.     descPtr->flags |= FSDM_FD_SIZE_DIRTY;
  623.  
  624. exit:
  625.     /*
  626.      * Make sure we really deleted the file if size is zero.
  627.      */
  628.     if (size == 0) {
  629.     register int index;
  630.  
  631.     for (index=0 ; index < FSDM_NUM_DIRECT_BLOCKS ; index++) {
  632.         if (descPtr->direct[index] != FSDM_NIL_INDEX) {
  633.         printf("Ofs_FileTrunc abandoning (direct) block %d in <%d,%d> \"%s\" savedLastByte %d\n",
  634.             descPtr->direct[index],
  635.             handlePtr->hdr.fileID.major, handlePtr->hdr.fileID.minor,
  636.             Fsutil_HandleName((Fs_HandleHeader *)handlePtr),
  637.             savedLastByte);
  638.         descPtr->direct[index] = FSDM_NIL_INDEX;
  639.         }
  640.     }
  641.     for (index = 0 ; index <= 2 ; index++) {
  642.         if (descPtr->indirect[index] != FSDM_NIL_INDEX) {
  643.         printf("Ofs_FileTrunc abandoning (indirect) block %d in <%d,%d> \"%s\" savedLastByte %d\n",
  644.             descPtr->indirect[index], 
  645.             handlePtr->hdr.fileID.major, handlePtr->hdr.fileID.minor,
  646.             Fsutil_HandleName((Fs_HandleHeader *)handlePtr),
  647.             savedLastByte);
  648.         descPtr->indirect[index] = FSDM_NIL_INDEX;
  649.         }
  650.     }
  651.     }
  652.     return(status);
  653. }
  654.  
  655.  
  656.  
  657.  
  658. /*
  659.  *----------------------------------------------------------------------
  660.  *
  661.  * OfsWriteBackDataBlockBitmap --
  662.  *
  663.  *    Write the data block bit map to disk.
  664.  *
  665.  * Results:
  666.  *    None.
  667.  *
  668.  * Side effects:
  669.  *    None.
  670.  *
  671.  *----------------------------------------------------------------------
  672.  */
  673. ENTRY ReturnStatus
  674. OfsWriteBackDataBlockBitmap(ofsPtr)
  675.     register    Ofs_Domain    *ofsPtr;    /* Domain for which to write 
  676.                          * back the bitmap. */
  677. {
  678.     ReturnStatus    status;
  679.  
  680.     LOCK_MONITOR;
  681.  
  682.     status = OfsDeviceBlockIO(ofsPtr, FS_WRITE, 
  683.             ofsPtr->headerPtr->bitmapOffset * 4, 
  684.             ofsPtr->headerPtr->bitmapBlocks * 4,
  685.             (Address) ofsPtr->dataBlockBitmap);
  686.     if (status != SUCCESS) {
  687.     printf( "OfsWriteBackDataBlockBitmap: Could not write out data block bitmap.\n");
  688.     }
  689.  
  690.     UNLOCK_MONITOR;
  691.     return(status);
  692. }
  693.  
  694.  
  695. /*
  696.  *----------------------------------------------------------------------
  697.  *
  698.  * OfsWriteBackSummaryInfo --
  699.  *
  700.  *    Write summary info to disk.
  701.  *
  702.  * Results:
  703.  *    None.
  704.  *
  705.  * Side effects:
  706.  *    None.
  707.  *
  708.  *----------------------------------------------------------------------
  709.  */
  710. ENTRY ReturnStatus
  711. OfsWriteBackSummaryInfo(ofsPtr)
  712.     register    Ofs_Domain    *ofsPtr;    /* Domain for which to write 
  713.                          * back the bitmap. */
  714. {
  715.     ReturnStatus    status;
  716.     Fs_IOParam        io;
  717.     Fs_IOReply        reply;
  718.  
  719.     LOCK_MONITOR;
  720.  
  721.     bzero((Address)&io, sizeof(io));
  722.     bzero((Address)&reply, sizeof(reply));
  723.     io.buffer = (Address)ofsPtr->summaryInfoPtr;
  724.     io.length = DEV_BYTES_PER_SECTOR;
  725.     io.offset = ofsPtr->summarySector * DEV_BYTES_PER_SECTOR;
  726.     status = (*devFsOpTable[DEV_TYPE_INDEX(ofsPtr->headerPtr->device.type)].write)
  727.         (&ofsPtr->headerPtr->device, &io, &reply); 
  728.     if (status != SUCCESS) {
  729.     printf("OfsWriteBackSummaryInfo: Could not write out summary info.\n");
  730.     }
  731.     if (status == GEN_NO_PERMISSION) {
  732.     printf("OfsWriteBackSummaryInfo: Disk is write-protected.\n");
  733.     status = SUCCESS;
  734.     }
  735.     UNLOCK_MONITOR;
  736.     return(status);
  737. }
  738.  
  739.  
  740. /*
  741.  *----------------------------------------------------------------------
  742.  *
  743.  * SelectCylinderInt --
  744.  *
  745.  *    Find a cylinder to use to allocate a block.  The search starts
  746.  *    with cylinderNum.  If it is full then it searches neighboring 
  747.  *    cylinders until it finds a cylinder with a free block.
  748.  *
  749.  * Results:
  750.  *    A cylinder number that contains a free block, -1 if none found.
  751.  *
  752.  * Side effects:
  753.  *    The free count on the found cylinder is decremented.
  754.  *
  755.  *----------------------------------------------------------------------
  756.  */
  757.  
  758. INTERNAL int
  759. SelectCylinderInt(hashSeed, ofsPtr, cylinderNum)
  760.     int                hashSeed;    /* Seed for the hash, usually
  761.                          * the file number. */
  762.     register    Ofs_Domain    *ofsPtr;    /* Domain to select cylinder 
  763.                          * from. */
  764.     int                cylinderNum;    /* Cylinder to try first, -1
  765.                          * if no preferred cylinder. */
  766. {
  767.     register    int        i;
  768.     register    OfsCylinder    *cylinderPtr;
  769.  
  770.     if (cylinderNum == -1) {
  771.     /*
  772.      * Do a random hash to find the starting point to allocate at.
  773.      */
  774.     fs_Stats.alloc.cylHashes++;
  775.     cylinderNum = ((hashSeed * 1103515245 + 12345) & 0x7fffffff) %
  776.                 ofsPtr->headerPtr->dataCylinders;
  777.     }
  778.  
  779.     /*
  780.      * Search forward starting at the desired cylinder.
  781.      */
  782.  
  783.     for (i = cylinderNum, cylinderPtr = &(ofsPtr->cylinders[cylinderNum]); 
  784.      i < ofsPtr->headerPtr->dataCylinders;
  785.      i++, cylinderPtr++) {
  786.     fs_Stats.alloc.cylsSearched++;
  787.     if (cylinderPtr->blocksFree > 0) {
  788.         ofsPtr->cylinders[i].blocksFree--;
  789.         return(i);
  790.     }
  791.     }
  792.  
  793.     /*
  794.      * No block forward from desired cylinder so search backward.
  795.      */
  796.  
  797.     for (i = cylinderNum - 1, 
  798.         cylinderPtr = &(ofsPtr->cylinders[cylinderNum - 1]);
  799.      i >= 0;
  800.      i--, cylinderPtr--) {
  801.     fs_Stats.alloc.cylsSearched++;
  802.     if (cylinderPtr->blocksFree > 0) {
  803.         ofsPtr->cylinders[i].blocksFree--;
  804.         return(i);
  805.     }
  806.     }
  807.  
  808.     return(-1);
  809. }
  810.  
  811.  
  812. /*
  813.  *----------------------------------------------------------------------
  814.  *
  815.  * FindBlockInt --
  816.  *
  817.  *    Search the bit map starting at the given cylinder for a free block.
  818.  *
  819.  * Results:
  820.  *    A logical 4K block number for the disk where the first data block 
  821.  *    is block 0 and a pointer into the bitmap for the block.
  822.  *
  823.  * Side effects:
  824.  *    If the allocate flag is set then the bit map is modified.
  825.  *
  826.  *----------------------------------------------------------------------
  827.  */
  828.  
  829. INTERNAL static void
  830. FindBlockInt(hashSeed, ofsPtr, nearBlock, allocate, blockNumPtr, 
  831.          bitmapPtrPtr)
  832.     int            hashSeed;    /* Seed for cylinder hash. */
  833.     register Ofs_Domain  *ofsPtr;     /* Domain to allocate blocks in. */
  834.     int            nearBlock;      /* Block number where this block should
  835.                      * be near. */
  836.     Boolean        allocate;       /* TRUE if allocating full block, FALSE
  837.                      * if intend to fragment block. */
  838.     int            *blockNumPtr;      /* Block number that was found. */
  839.     unsigned char    **bitmapPtrPtr;    /* Bit map entry that corresponds to
  840.                      * the block. */
  841. {
  842.     unsigned char *bitmapPtr;
  843.     int       blockNum;
  844.     int       block;
  845.     int       startingBlockOffset;
  846.     int               blocksPerCylinder;
  847.     int               mask;
  848.     int               cylinderNum;
  849.  
  850.     blocksPerCylinder = ofsPtr->headerPtr->geometry.blocksPerCylinder;
  851.     if (nearBlock != -1) {
  852.     cylinderNum = ((unsigned int) nearBlock) / blocksPerCylinder;
  853.     startingBlockOffset = ((unsigned int) nearBlock) % blocksPerCylinder;
  854.     } else {
  855.     cylinderNum = -1;
  856.     startingBlockOffset = -1;
  857.     }
  858.     cylinderNum = SelectCylinderInt(hashSeed, ofsPtr, cylinderNum);
  859.     if (cylinderNum == -1) {
  860.     *blockNumPtr = -1;
  861.     return;
  862.     }
  863.     if (ofs_AllocGap == 0) {
  864.     /*
  865.      * CONTIGUOUS allocation.
  866.      * This is the original code that simply starts at the beginning
  867.      * of the cylinder and stops when it finds a free block.
  868.      */
  869.     bitmapPtr = 
  870.       &(ofsPtr->dataBlockBitmap[cylinderNum * ofsPtr->bytesPerCylinder]);
  871.     blockNum = cylinderNum * blocksPerCylinder;
  872.     while (TRUE) {
  873.         fs_Stats.alloc.cylBitmapSearches++;
  874.         if (UpperBlockFree(*bitmapPtr)) {
  875.         mask = 0xf0;
  876.         break;
  877.         }
  878.         if (LowerBlockFree(*bitmapPtr)) {
  879.         mask = 0x0f;
  880.         blockNum++;
  881.         break;
  882.         }
  883.         bitmapPtr++;
  884.         blockNum += 2;
  885.     }
  886.     } else {
  887.     /*
  888.      * SKIP BLOCK allocation.
  889.      * startingBlockOffset is the offset of the last allocated block, or -1
  890.      * Set block to be ahead of the startingBlockOffset,
  891.      * and set the bitmapPtr to the corresponding spot in the bitmap.
  892.      */
  893.     if (startingBlockOffset >= 0) {
  894.         startingBlockOffset += 1;
  895.         block = startingBlockOffset + ofs_AllocGap;
  896.     } else {
  897.         block = 0;
  898.         startingBlockOffset = blocksPerCylinder;
  899.     }
  900.     bitmapPtr = 
  901.         &(ofsPtr->dataBlockBitmap[cylinderNum * ofsPtr->bytesPerCylinder
  902.                      + block / 2]);
  903.      /*
  904.      * Walk through the bitmap.  We are guaranteed from SelectCylinder that
  905.      * there is a free block in this cylinder.
  906.      * Each byte in the bitmap covers two 4K blocks.
  907.      * The 'UpperBlock' covered by the byte is an even numbered block,
  908.      * and the 'LowerBlock' is odd.
  909.      */
  910.     for ( ; block != startingBlockOffset; block++) {
  911.         fs_Stats.alloc.cylBitmapSearches++;
  912.         if (block >= blocksPerCylinder) {
  913.          /*
  914.           * Wrap back to the beginning of the cylinder
  915.           */
  916.          block -= blocksPerCylinder;
  917.          bitmapPtr -= ofsPtr->bytesPerCylinder;
  918.         }
  919.         if ((block & 0x1) == 0 && UpperBlockFree(*bitmapPtr)) {
  920.         mask = 0xf0;
  921.         goto haveFreeBlock;
  922.         }
  923.         if ((block & 0x1) != 0 && LowerBlockFree(*bitmapPtr)) {
  924.         mask = 0x0f;
  925.         goto haveFreeBlock;
  926.         }
  927.         if (block & 0x1) {
  928.         bitmapPtr++;
  929.         }
  930.     }
  931.     UNLOCK_MONITOR;
  932.     panic("FindBlockInt: no block\n");
  933.     *blockNumPtr = -1;
  934.     ofs_AllocGap = CONTIGUOUS;
  935.     LOCK_MONITOR;
  936.     return;
  937.  
  938. haveFreeBlock:
  939.     blockNum = cylinderNum * blocksPerCylinder + block;
  940.     }
  941.     if (allocate) {
  942.     if (*bitmapPtr & mask) {
  943.         printf("bitmap = <%x>, checkMask = <%x>\n",
  944.                    *bitmapPtr & 0xff, mask & 0xff);
  945.         printf("FsFindBlockInt, error in {Upper/Lower}BlockFree, failing.\n");
  946.         *blockNumPtr = -1;
  947.         return;
  948.     }
  949.     *bitmapPtr |= mask;
  950.     }
  951.  
  952.     *bitmapPtrPtr = bitmapPtr;
  953.     *blockNumPtr = blockNum;
  954.     fs_Stats.alloc.blocksAllocated++;
  955. }
  956.  
  957.  
  958. /*
  959.  *----------------------------------------------------------------------
  960.  *
  961.  * OfsBlockFind --
  962.  *
  963.  *    Search the bit map starting at the given cylinder for a free block.
  964.  *
  965.  * Results:
  966.  *    Results from FindBlockInt.
  967.  *
  968.  * Side effects:
  969.  *    None.
  970.  *
  971.  *----------------------------------------------------------------------
  972.  */
  973. ENTRY void
  974. OfsBlockFind(hashSeed, ofsPtr, nearBlock, allocate, blockNumPtr, bitmapPtrPtr)
  975.     int            hashSeed;    /* Seed for cylinder hash. */
  976.     Ofs_Domain     *ofsPtr;     /* Domain to allocate blocks in . */
  977.     int            nearBlock;      /* Block number where this block should
  978.                      * be near. */
  979.     Boolean        allocate;       /* TRUE if allocating full block, FALSE
  980.                      * if intend to fragment block. */
  981.     int            *blockNumPtr;      /* Block number that was found. */
  982.     unsigned char    **bitmapPtrPtr;    /* Bit map entry that corresponds to
  983.                      * the block. */
  984. {
  985.     LOCK_MONITOR;
  986.  
  987.     if (ofsPtr->summaryInfoPtr->numFreeKbytes - FS_FRAGMENTS_PER_BLOCK <
  988.         ofsPtr->minKFree) {
  989.     *blockNumPtr = -1;
  990.     UNLOCK_MONITOR;
  991.     return;
  992.     }
  993.  
  994.     FindBlockInt(hashSeed, ofsPtr, nearBlock, allocate, blockNumPtr, 
  995.          bitmapPtrPtr);
  996.     if (*blockNumPtr != -1) {
  997.     ofsPtr->summaryInfoPtr->numFreeKbytes -= FS_FRAGMENTS_PER_BLOCK;
  998.     }
  999.  
  1000.     UNLOCK_MONITOR;
  1001. }
  1002.  
  1003.  
  1004. /*
  1005.  *----------------------------------------------------------------------
  1006.  *
  1007.  * OfsBlockFree --
  1008.  *
  1009.  *    Put the given block back into the bit map.
  1010.  *
  1011.  * Results:
  1012.  *    None.
  1013.  *
  1014.  * Side effects:
  1015.  *    The bit map is modified.
  1016.  *
  1017.  *----------------------------------------------------------------------
  1018.  */
  1019.  
  1020. ENTRY void
  1021. OfsBlockFree(ofsPtr, blockNum)
  1022.     register Ofs_Domain *ofsPtr;     /* Handle for file to alloc blocks 
  1023.                      * for. */
  1024.     int              blockNum;       /* Block number to free. */
  1025. {
  1026.     register unsigned char *bitmapPtr;
  1027.     int               cylinderNum;
  1028.     register int       mask;
  1029.     register int       checkMask;
  1030.  
  1031.     LOCK_MONITOR;
  1032.  
  1033.     ofsPtr->summaryInfoPtr->numFreeKbytes += FS_FRAGMENTS_PER_BLOCK;
  1034.     fs_Stats.alloc.blocksFreed++;
  1035.     bitmapPtr = GetBitmapPtr(ofsPtr, blockNum);
  1036.     cylinderNum = (unsigned int) blockNum / 
  1037.             ofsPtr->headerPtr->geometry.blocksPerCylinder;
  1038.     ofsPtr->cylinders[cylinderNum].blocksFree++;
  1039.     if ((blockNum % ofsPtr->headerPtr->geometry.blocksPerCylinder) & 0x1) {
  1040.     mask = 0xf0;
  1041.     } else {
  1042.     mask = 0x0f;
  1043.     }
  1044.     checkMask = ~mask & 0xff;
  1045.     if ((*bitmapPtr & checkMask) != checkMask) {
  1046.     printf("bitmap = <%x>, checkMask = <%x>\n",
  1047.                *bitmapPtr & 0xff, checkMask & 0xff);
  1048.         UNLOCK_MONITOR;
  1049.     printf("OfsBlockFree free block %d\n", blockNum);
  1050.     return;
  1051.     } else {
  1052.     *bitmapPtr &= mask;
  1053.     }
  1054.  
  1055.     UNLOCK_MONITOR;
  1056. }
  1057.  
  1058.  
  1059. /*
  1060.  *----------------------------------------------------------------------
  1061.  *
  1062.  * OfsFragFind --
  1063.  *
  1064.  *    Allocate a fragment out of the bit map.  If possible the fragment
  1065.  *    is allocated where the last fragment was allocated.
  1066.  *
  1067.  * Results:
  1068.  *    A logical block number and offset into the block where the
  1069.  *    fragment begins.
  1070.  *
  1071.  * Side effects:
  1072.  *    The bit map and the fragment lists might be modified.
  1073.  *
  1074.  *----------------------------------------------------------------------
  1075.  */
  1076.  
  1077. ENTRY void
  1078. OfsFragFind(hashSeed, ofsPtr, numFrags, lastFragBlock, lastFragOffset, 
  1079.         lastFragSize, newFragBlockPtr, newFragOffsetPtr)
  1080.     int            hashSeed;        /* Seed for cylinder hash. */
  1081.     register Ofs_Domain *ofsPtr;        /* Domain out of which to 
  1082.                          * allocate the fragment. */
  1083.     int                  numFrags;           /* Number of fragments to get: 
  1084.                          * 1, 2, or 3 */
  1085.     int                  lastFragBlock;        /* Block number where the last 
  1086.                          * fragment for this file was 
  1087.                          * allocated. */
  1088.     int                  lastFragOffset;        /* Fragment offset in the 
  1089.                          * block. */
  1090.     int                  lastFragSize;        /* Number of fragments in the 
  1091.                          * last fragment. */
  1092.     int                  *newFragBlockPtr;    /* Where to return new fragment
  1093.                              * block number. */
  1094.     int                  *newFragOffsetPtr;    /* Where to return new fragment
  1095.                          * offset. */
  1096. {
  1097.     register OfsFragment          *fragPtr;
  1098.     register unsigned char     *bitmapPtr = (unsigned char *) NIL;
  1099.     register int           *savedOffsets;
  1100.     unsigned char        savedBitmap;
  1101.     int                   *fragOffsetPtr;
  1102.     int                   fragOffset = 0;
  1103.     int                   fragBlock;
  1104.     unsigned char            *tBitmapPtr;
  1105.     List_Links                  *fragList;
  1106.     int                   byteOffset;
  1107.     int                   fragMask = 0;
  1108.     int                   i;
  1109.     int                   blockNum = -1;
  1110.     int                fragsToAllocate;
  1111.  
  1112.     LOCK_MONITOR;
  1113.  
  1114.     if (lastFragBlock == -1)  {
  1115.     fragsToAllocate = numFrags;
  1116.     } else {
  1117.     fragsToAllocate = numFrags - lastFragSize;
  1118.     }
  1119.     if (ofsPtr->summaryInfoPtr->numFreeKbytes - fragsToAllocate <
  1120.         ofsPtr->minKFree) {
  1121.     *newFragBlockPtr = -1;
  1122.     UNLOCK_MONITOR;
  1123.     return;
  1124.     }
  1125.  
  1126.     /*
  1127.      * First try the block where the last fragment was.
  1128.      */
  1129.  
  1130.     fs_Stats.alloc.fragsAllocated++;
  1131.     if (lastFragBlock != -1 && 
  1132.     lastFragOffset + numFrags <= FS_FRAGMENTS_PER_BLOCK ) {
  1133.     fs_Stats.alloc.fragUpgrades++;
  1134.     bitmapPtr = GetBitmapPtr(ofsPtr, lastFragBlock);
  1135.     if ((lastFragBlock % ofsPtr->headerPtr->geometry.blocksPerCylinder)
  1136.         & 0x1) {
  1137.         byteOffset = lastFragOffset + 4;
  1138.     } else {
  1139.         byteOffset = lastFragOffset;
  1140.     }
  1141.     fragMask = 0;
  1142.     blockNum = lastFragBlock;
  1143.     fragOffset = lastFragOffset;
  1144.     /*
  1145.      * Now make sure that there are enough free fragments in the block. 
  1146.      */
  1147.     for (i = byteOffset + lastFragSize; i < byteOffset + numFrags; i++) {
  1148.         if (*bitmapPtr & bitMasks[i]) {
  1149.         blockNum = -1;
  1150.         break;
  1151.         }
  1152.         fragMask |= bitMasks[i];
  1153.     }
  1154.     }
  1155.  
  1156.     if (blockNum == -1) {
  1157.     /* 
  1158.      * We couldn't find space in the block where the last fragment was.
  1159.      * First try all fragment lists starting with the one of the 
  1160.      * desired size.
  1161.      */
  1162.  
  1163.     for (i = numFrags - 1; 
  1164.          i < OFS_NUM_FRAG_SIZES && blockNum == -1; 
  1165.          i++) {
  1166.         fragList = ofsPtr->fragLists[i];
  1167.         while (!List_IsEmpty(fragList)) {
  1168.         fragPtr = (OfsFragment *) List_First(fragList);
  1169.         List_Remove((List_Links *) fragPtr);
  1170.         fragBlock = fragPtr->blockNum;
  1171.         free((Address) fragPtr);
  1172.         /*
  1173.          * Check to make sure that there really is a fragment of the
  1174.          * needed size in the block.  These fragment lists are hints.
  1175.          */
  1176.         bitmapPtr = GetBitmapPtr(ofsPtr, fragBlock);
  1177.         if ((fragBlock %
  1178.              ofsPtr->headerPtr->geometry.blocksPerCylinder) & 0x1) {
  1179.             fragOffset = fragTable[GetLowerFragMask(*bitmapPtr)][i];
  1180.         } else {
  1181.             fragOffset = fragTable[GetUpperFragMask(*bitmapPtr)][i];
  1182.         }
  1183.         if (fragOffset != -1) {
  1184.             /*
  1185.              * There is a fragment of this size so use this block.
  1186.              */
  1187.             blockNum = fragBlock;
  1188.             break;
  1189.         } else {
  1190.             fs_Stats.alloc.badFragList++;
  1191.         }
  1192.         }
  1193.     }
  1194.  
  1195.     if (blockNum == -1) {
  1196.         fs_Stats.alloc.fullBlockFrags++;
  1197.         /*
  1198.          * We couldn't find a fragmented block to use so have to 
  1199.          * fragment a full block.
  1200.          */
  1201.         FindBlockInt(hashSeed, ofsPtr, -1, FALSE, &blockNum, 
  1202.              &tBitmapPtr);
  1203.         if (blockNum == -1) {
  1204.         *newFragBlockPtr = -1;
  1205.         UNLOCK_MONITOR;
  1206.         return;
  1207.         }
  1208.         bitmapPtr = tBitmapPtr;
  1209.         fragOffset = 0;
  1210.     }
  1211.     /*
  1212.      * See if the block number corresponds to the high or low
  1213.      * end of the bitmap byte.  If, for example, there are an odd
  1214.      * number of blocks per cylinder, an even block number may be
  1215.      * odd relative to the start of the cylinder, and relative to
  1216.      * the start of the bitmap for that cylinder.
  1217.      */
  1218.     if ((blockNum % ofsPtr->headerPtr->geometry.blocksPerCylinder)
  1219.         & 0x1) {
  1220.         byteOffset = fragOffset + 4;
  1221.     } else {
  1222.         byteOffset = fragOffset;
  1223.     }
  1224.     fragMask = 0;
  1225.     for (i = byteOffset; i < byteOffset + numFrags; i++) {
  1226.         fragMask |= bitMasks[i];
  1227.     }
  1228.     ofsPtr->summaryInfoPtr->numFreeKbytes -= numFrags;
  1229.     } else {
  1230.     ofsPtr->summaryInfoPtr->numFreeKbytes -= numFrags - lastFragSize;
  1231.     fs_Stats.alloc.fragsUpgraded++;
  1232.     }
  1233.  
  1234.     /*
  1235.      * Now put the block on all appropriate fragment lists.  savedOffsets 
  1236.      * points to the fragment offsets before we allocated the new fragment out
  1237.      * of the block.  fragOffsetPtr points to the fragment offset after
  1238.      * we allocated the fragment out of the block.
  1239.      */
  1240.  
  1241.     if (*bitmapPtr & fragMask) {
  1242.     UNLOCK_MONITOR;
  1243.     panic("Find frag bitmap error\n");
  1244.     *newFragBlockPtr = -1;
  1245.     return;
  1246.     } else {
  1247.     savedBitmap = *bitmapPtr;
  1248.     *bitmapPtr |= fragMask;
  1249.     }
  1250.     if ((blockNum % ofsPtr->headerPtr->geometry.blocksPerCylinder) & 0x1) {
  1251.     savedOffsets = fragTable[GetLowerFragMask(savedBitmap)];
  1252.     fragOffsetPtr = fragTable[GetLowerFragMask(*bitmapPtr)];
  1253.     } else {
  1254.     savedOffsets = fragTable[GetUpperFragMask(savedBitmap)];
  1255.     fragOffsetPtr = fragTable[GetUpperFragMask(*bitmapPtr)];
  1256.     }
  1257.     for (i = 0; i < OFS_NUM_FRAG_SIZES; i++, savedOffsets++, fragOffsetPtr++) {
  1258.     if (*savedOffsets == -1 && *fragOffsetPtr != -1) {
  1259.         /*
  1260.          * The block was not on the fragment list of this size before we
  1261.          * allocated a new fragment out of it, so put it there. 
  1262.          */
  1263.         fragPtr = (OfsFragment *) malloc(sizeof(OfsFragment));
  1264.         List_Insert((List_Links *) fragPtr, 
  1265.             LIST_ATREAR(ofsPtr->fragLists[i]));
  1266.         fragPtr->blockNum = blockNum;
  1267.     }
  1268.     }
  1269.  
  1270.     *newFragBlockPtr = blockNum;
  1271.     *newFragOffsetPtr = fragOffset;
  1272.  
  1273.     if (fragOffset + numFrags > FS_FRAGMENTS_PER_BLOCK) {
  1274.     UNLOCK_MONITOR;
  1275.     panic("FsdmFragFind, fragment overrun, offset %d numFrags %d\n",
  1276.             fragOffset, numFrags);
  1277.     return;
  1278.     }
  1279.  
  1280.     UNLOCK_MONITOR;
  1281. }
  1282.  
  1283.  
  1284. /*
  1285.  *----------------------------------------------------------------------
  1286.  *
  1287.  * OfsFragFree --
  1288.  *
  1289.  *    Free the given fragment.
  1290.  *
  1291.  * Results:
  1292.  *    None.
  1293.  *
  1294.  * Side effects:
  1295.  *    The bit map and fragment lists are modified.
  1296.  *
  1297.  *----------------------------------------------------------------------
  1298.  */
  1299.  
  1300. ENTRY void
  1301. OfsFragFree(ofsPtr, numFrags, fragBlock, fragOffset) 
  1302.     register Ofs_Domain *ofsPtr;    /* Domain out of which to allocate the
  1303.                        fragment. */
  1304.     int              numFrags;     /* Number of fragments to free: 1, 2,
  1305.                        or 3 */
  1306.     int              fragBlock;    /* Block number where the fragment
  1307.                        was allocated. */
  1308.     int              fragOffset;    /* Fragment offset in the block. */
  1309. {
  1310.     register int       *fragOffsets;
  1311.     register int        *savedOffsets;
  1312.     register unsigned char *bitmapPtr;
  1313.     OfsFragment           *fragPtr;
  1314.     unsigned char         mask;
  1315.     int                    i;
  1316.     int                    byteOffset;
  1317.     int                fragMask;
  1318.  
  1319.     LOCK_MONITOR;
  1320.  
  1321.     fs_Stats.alloc.fragsFreed++;
  1322.  
  1323.     ofsPtr->summaryInfoPtr->numFreeKbytes += numFrags;
  1324.  
  1325.     bitmapPtr = GetBitmapPtr(ofsPtr, fragBlock);
  1326.  
  1327.     /*
  1328.      * Determine whether should clear upper or lower 4 bits.
  1329.      */
  1330.  
  1331.     if ((fragBlock % ofsPtr->headerPtr->geometry.blocksPerCylinder) & 0x1) {
  1332.     byteOffset = fragOffset + 4;
  1333.     savedOffsets = fragTable[GetLowerFragMask(*bitmapPtr)];
  1334.     } else {
  1335.     byteOffset = fragOffset;
  1336.     savedOffsets = fragTable[GetUpperFragMask(*bitmapPtr)];
  1337.     }
  1338.  
  1339.     /*
  1340.      * Determine the bits to unset and unset them.
  1341.      */
  1342.  
  1343.     mask = 0;
  1344.     for (i = byteOffset; i < byteOffset + numFrags; i++) {
  1345.     mask |= bitMasks[i];
  1346.     }
  1347.     if ((*bitmapPtr & mask) != mask) {
  1348.     printf("OfsFragFree: bitmap = <%x>, checkMask = <%x>\n",
  1349.                *bitmapPtr & 0xff, mask & 0xff);
  1350.     UNLOCK_MONITOR;
  1351.     printf("OfsFragFree: block not free, block %d, numFrag %d, offset %d\n",
  1352.             fragBlock, numFrags, fragOffset);
  1353.     return;
  1354.     } else {
  1355.     *bitmapPtr &= ~mask;
  1356.     }
  1357.  
  1358.     /*
  1359.      * Determine the new state of the block and put things onto the
  1360.      * proper fragment lists.  savedOffsets points to the array of frag
  1361.      * offsets before we freed the fragment in the block and fragOffsets
  1362.      * points to the frag offsets after we freed the fragment.
  1363.      */
  1364.  
  1365.     if ((fragBlock % ofsPtr->headerPtr->geometry.blocksPerCylinder) & 0x1) {
  1366.     fragMask = GetLowerFragMask(*bitmapPtr);
  1367.     } else {
  1368.     fragMask = GetUpperFragMask(*bitmapPtr);
  1369.     }
  1370.     if (fragMask == 0) {
  1371.     fs_Stats.alloc.fragToBlock++;
  1372.     /*
  1373.      * The block has become totally free.
  1374.      */
  1375.     ofsPtr->cylinders[(unsigned int) fragBlock / 
  1376.          ofsPtr->headerPtr->geometry.blocksPerCylinder].blocksFree++;
  1377.     UNLOCK_MONITOR;
  1378.     return;
  1379.     }
  1380.     fragOffsets = fragTable[fragMask];
  1381.     for (i = 0; i < OFS_NUM_FRAG_SIZES; i++, fragOffsets++, savedOffsets++) {
  1382.     if (*savedOffsets == -1 && *fragOffsets != -1) {
  1383.         /*
  1384.          * A fragment of this size did not exist before we freed the 
  1385.          * fragment but it does exist now.
  1386.          */
  1387.         fragPtr = (OfsFragment *) malloc(sizeof(OfsFragment));
  1388.         List_Insert((List_Links *) fragPtr, 
  1389.                 LIST_ATREAR(ofsPtr->fragLists[i]));
  1390.         fragPtr->blockNum = fragBlock;
  1391.     }
  1392.     }
  1393.  
  1394.     UNLOCK_MONITOR;
  1395. }
  1396.  
  1397.  
  1398. /*
  1399.  *----------------------------------------------------------------------
  1400.  *
  1401.  * OnlyFrag --
  1402.  *
  1403.  *    Determine if the given fragment is the only one in the block.
  1404.  *
  1405.  * Results:
  1406.  *    TRUE if the given fragment is the only one in the block.
  1407.  *
  1408.  * Side effects:
  1409.  *    The rest of the block is marked as allocated if the given fragment
  1410.  *    is the only one in the block.
  1411.  *
  1412.  *----------------------------------------------------------------------
  1413.  */
  1414.  
  1415. ENTRY Boolean
  1416. OnlyFrag(ofsPtr, numFrags, fragBlock, fragOffset) 
  1417.     register Ofs_Domain *ofsPtr;    /* Domain of fragment. */
  1418.     int              numFrags;     /* Number of fragments to free: 1, 2,
  1419.                        or 3 */
  1420.     int              fragBlock;    /* Block number where the fragment
  1421.                        was allocated. */
  1422.     int              fragOffset;    /* Fragment offset in the block. */
  1423. {
  1424.     register unsigned char    *bitmapPtr;
  1425.     unsigned char          mask;
  1426.     int                        i;
  1427.     int                        byteOffset;
  1428.     int                blockMask;
  1429.  
  1430.     LOCK_MONITOR;
  1431.  
  1432.     bitmapPtr = GetBitmapPtr(ofsPtr, fragBlock);
  1433.  
  1434.     /*
  1435.      * Determine whether should access upper or lower 4 bits.
  1436.      */
  1437.     if ((fragBlock % ofsPtr->headerPtr->geometry.blocksPerCylinder) & 0x1) {
  1438.     byteOffset = fragOffset + 4;
  1439.     blockMask = 0x0f;
  1440.     } else {
  1441.     byteOffset = fragOffset;
  1442.     blockMask = 0xf0;
  1443.     }
  1444.  
  1445.     /*
  1446.      * Determine which bits are set for this fragment.
  1447.      */
  1448.     mask = 0;
  1449.     for (i = byteOffset; i < byteOffset + numFrags; i++) {
  1450.     mask |= bitMasks[i];
  1451.     }
  1452.     if ((*bitmapPtr & mask) != mask) {
  1453.     printf("bitmap = <%x>, checkMask = <%x>\n",
  1454.                *bitmapPtr & 0xff, mask & 0xff);
  1455.     UNLOCK_MONITOR;
  1456.     panic("OnlyFrag: Frag block corrupted.\n");
  1457.     return(FALSE);
  1458.     }
  1459.     if (((*bitmapPtr & ~mask) & blockMask) != 0) {
  1460.     /*
  1461.      * There is another fragment in this block so we can't put the block
  1462.      * into the bad block file yet.
  1463.      */
  1464.     UNLOCK_MONITOR;
  1465.     return(FALSE);
  1466.     }
  1467.  
  1468.     /*
  1469.      * We were the only fragment in this block.  Mark the rest of the block
  1470.      * as allocated because our caller is going to put this block into the
  1471.      * bad block file.
  1472.      */
  1473.     *bitmapPtr |= blockMask;
  1474.     ofsPtr->summaryInfoPtr->numFreeKbytes -= 
  1475.                     FS_FRAGMENTS_PER_BLOCK - numFrags;
  1476.  
  1477.     UNLOCK_MONITOR;
  1478.     return(TRUE);
  1479. }
  1480.  
  1481. /*
  1482.  *----------------------------------------------------------------------
  1483.  *
  1484.  * UpgradeFragment --
  1485.  *
  1486.  *    Take a fragment and make it of sufficient size to fit the new
  1487.  *    fragment size.
  1488.  *
  1489.  * Results:
  1490.  *    SUCCESS, FS_NO_DISK_SPACE, or FS_WOULD_BLOCK (if cache is full).
  1491.  *
  1492.  * Side effects:
  1493.  *    *indexInfoPtr may be modified along with *indexInfoPtr->blockAddrPtr.
  1494.  *
  1495.  *----------------------------------------------------------------------
  1496.  */
  1497.  
  1498. static ReturnStatus
  1499. UpgradeFragment(ofsPtr, handlePtr, indexInfoPtr, curLastBlock, newLastFrag, 
  1500.         dontWriteThru, dontBlock, dirtiedIndexPtr)
  1501.     Ofs_Domain        *ofsPtr;        /* Domain of file. */
  1502.     Fsio_FileIOHandle        *handlePtr;    /* File to allocate blocks 
  1503.                          * for. */
  1504.     register OfsBlockIndexInfo *indexInfoPtr;    /* Index info structure. */
  1505.     int            curLastBlock;        /* The current last block. */
  1506.     int            newLastFrag;        /* New last fragment for this
  1507.                          * file.  Fragments are numbered
  1508.                          * from 0. */
  1509.     Boolean        dontWriteThru;        /* TRUE => make sure that the
  1510.                          * cache block that contains
  1511.                          * upgraded block isn't forced
  1512.                          * through to disk. */
  1513.     int            dontBlock;        /* FSCACHE_DONT_BLOCK */
  1514.     Boolean        *dirtiedIndexPtr;     /* TRUE if modified the block 
  1515.                          * pointer in the file index 
  1516.                          * structure. */
  1517. {
  1518.     register    Fsdm_FileDescriptor *descPtr;
  1519.     register    int          blockAddr;
  1520.     int                 curLastFrag;    /* Current last fragment for
  1521.                          * this file. */
  1522.     int                 curFragBlock;    /* Current disk block used for 
  1523.                          * last block in file. */
  1524.     int                 curFragOffset;    /* Offset in the block where
  1525.                          * the fragment begins. */
  1526.     int                 newFragBlock;    /* New disk block used for last
  1527.                            block in file. */
  1528.     int                 newFragOffset;    /* Offset in new block where 
  1529.                          * the fragment begins. */
  1530.     unsigned char          *bitmapPtr;
  1531.     Fscache_Block         *fragCacheBlockPtr;
  1532.     Boolean             found;
  1533.     ReturnStatus         status = SUCCESS;
  1534.     int                 flags;
  1535.  
  1536.     descPtr = handlePtr->descPtr;
  1537.     blockAddr = *(indexInfoPtr->blockAddrPtr);
  1538.  
  1539.     curLastFrag = (unsigned int) (descPtr->lastByte & FS_BLOCK_OFFSET_MASK) /
  1540.                     FS_FRAGMENT_SIZE;
  1541.  
  1542.     if (curLastBlock >= FSDM_NUM_DIRECT_BLOCKS || curLastFrag == LAST_FRAG ||
  1543.     curLastFrag >= newLastFrag) {
  1544.     /*
  1545.      * There is already enough space so return.
  1546.      */
  1547.     goto exit;
  1548.     }
  1549.     curFragBlock = (unsigned int) blockAddr / FS_FRAGMENTS_PER_BLOCK;
  1550.     curFragOffset = blockAddr & FRAG_OFFSET_MASK;
  1551.     if (newLastFrag < LAST_FRAG) {
  1552.     /*
  1553.      * Have to allocate a larger fragment.  Note that fragments are
  1554.      * numbered from zero so that the fragment number + 1 is equal to the
  1555.      * number of fragments in the block.
  1556.      */
  1557.     OfsFragFind(handlePtr->hdr.fileID.minor, ofsPtr, newLastFrag + 1, 
  1558.             curFragBlock, curFragOffset, curLastFrag + 1,
  1559.             &newFragBlock, &newFragOffset);
  1560.     if (newFragBlock == -1) {
  1561.         printf("UpgradeFragment: OfsFragFind failed: no space on %s.\n",
  1562.            ofsPtr->domainPtr->domainPrefix); /* DEBUG */
  1563.         status = FS_NO_DISK_SPACE;
  1564.         goto exit;
  1565.     }
  1566.     if (curFragBlock == newFragBlock && curFragOffset == newFragOffset) {
  1567.         /*
  1568.          * Were able to extend the old fragment so return.
  1569.          */
  1570.         descPtr->numKbytes += newLastFrag - curLastFrag;
  1571.         goto exit;
  1572.     }
  1573.     } else {
  1574.     /*
  1575.      * Allocate a full block.
  1576.      */
  1577.     OfsBlockFind(handlePtr->hdr.fileID.minor, ofsPtr,
  1578.             indexInfoPtr->lastDiskBlock,
  1579.             TRUE, &newFragBlock, &bitmapPtr);
  1580.     if (newFragBlock == -1) {
  1581.         printf("UpgradeFragment: OfsBlockFind failed: no space on %s.\n",
  1582.            ofsPtr->domainPtr->domainPrefix); /* DEBUG */
  1583.         status = FS_NO_DISK_SPACE;
  1584.         goto exit;
  1585.     } else if (newFragBlock == 0 && handlePtr->hdr.fileID.minor != 2) {
  1586.         printf("UpgradeFragment: tried to allocate block 0 to non-root file #%d\n",
  1587.             handlePtr->hdr.fileID.minor);
  1588.         status = FAILURE;
  1589.         goto exit;
  1590.     }
  1591.     newFragOffset = 0;
  1592.     }
  1593.         
  1594.     /*
  1595.      * Copy over the old fragment into the new larger one.  This
  1596.      * is done by fetching the block into the cache, switching the value in 
  1597.      * the file descriptor and marking the block dirty.
  1598.      */
  1599.     Fscache_FetchBlock(&handlePtr->cacheInfo, 
  1600.               curLastBlock, FSCACHE_DATA_BLOCK | dontBlock,
  1601.               &fragCacheBlockPtr, &found);
  1602.     if (fragCacheBlockPtr == (Fscache_Block *)NIL) {
  1603.     status = FS_WOULD_BLOCK;
  1604.     goto exit;
  1605.     }
  1606.     fs_Stats.blockCache.fragAccesses++;
  1607.     if (!found) {
  1608.     status = OfsDeviceBlockIO(ofsPtr, FS_READ, 
  1609.            blockAddr +
  1610.            ofsPtr->headerPtr->dataOffset * FS_FRAGMENTS_PER_BLOCK,
  1611.            curLastFrag + 1, fragCacheBlockPtr->blockAddr);
  1612.     if (status != SUCCESS) {
  1613.         Fscache_UnlockBlock(fragCacheBlockPtr, 0, -1, 0, 0);
  1614.         OfsFragFree(ofsPtr, newLastFrag + 1, 
  1615.                newFragBlock, newFragOffset);
  1616.         goto exit;
  1617.     }
  1618.     fs_Stats.blockCache.fragZeroFills++;
  1619.     /*
  1620.      * Zero fill the rest of the block.
  1621.      */
  1622.     bzero(fragCacheBlockPtr->blockAddr +
  1623.             (curLastFrag + 1) * FS_FRAGMENT_SIZE,
  1624.         FS_BLOCK_SIZE - (curLastFrag + 1) * FS_FRAGMENT_SIZE);
  1625.     } else {
  1626.     fs_Stats.blockCache.fragHits++;
  1627.     if (fragCacheBlockPtr->flags & FSCACHE_READ_AHEAD_BLOCK) {
  1628.         fs_Stats.blockCache.readAheadHits++;
  1629.     }
  1630.     }
  1631.     /*
  1632.      * Commit the change in the fragments location.
  1633.      * 1 - unlock the cache block, specifying the new location.
  1634.      *        This step blocks if I/O is in progress on the block.
  1635.      *        After any I/O (such as a writeback) completes, then
  1636.      *        the block will be put on the dirty list with the new address.
  1637.      * 2 - update the file descriptors indexing information to point to
  1638.      *        the new block.
  1639.      * 3 - free up the old fragment.
  1640.      *
  1641.      * (As a historical note, steps 1 & 2 used to be reversed.  Files
  1642.      *    were ending up with the wrong trailing fragment occasionally.)
  1643.      */
  1644.  
  1645.     if (dontWriteThru) {
  1646.     flags = FSCACHE_CLEAR_READ_AHEAD | FSCACHE_DONT_WRITE_THRU;
  1647.     } else {
  1648.     flags = FSCACHE_CLEAR_READ_AHEAD;
  1649.     }
  1650.     blockAddr = newFragBlock * FS_FRAGMENTS_PER_BLOCK + newFragOffset;
  1651.     Fscache_UnlockBlock(fragCacheBlockPtr, (unsigned) Fsutil_TimeInSeconds(), 
  1652.                blockAddr, 
  1653.                (newLastFrag + 1) * FS_FRAGMENT_SIZE, flags);
  1654.  
  1655.     *(indexInfoPtr->blockAddrPtr) = blockAddr;
  1656.     descPtr->numKbytes += newLastFrag - curLastFrag;
  1657.     descPtr->flags |= FSDM_FD_SIZE_DIRTY;
  1658.     *dirtiedIndexPtr = TRUE;
  1659.  
  1660.     OfsFragFree(ofsPtr, curLastFrag + 1, curFragBlock, curFragOffset);
  1661.  
  1662. exit:
  1663.     return(status);
  1664. }
  1665.  
  1666.  
  1667. /*
  1668.  *----------------------------------------------------------------------
  1669.  *
  1670.  * AllocateBlock --
  1671.  *
  1672.  *    Allocate a block for the file.
  1673.  *
  1674.  * Results:
  1675.  *    FS_NO_DISK_SPACE if could not allocate block.  Otherwise,
  1676.  *    returns SUCCESS.
  1677.  *
  1678.  * Side effects:
  1679.  *     Also *indexInfoPtr may be modified along with *indexInfoPtr->blockAddr.
  1680.  *
  1681.  *----------------------------------------------------------------------
  1682.  */
  1683.  
  1684. static ReturnStatus
  1685. AllocateBlock(handlePtr, descPtr, indexInfoPtr, newLastByte, curLastBlock, 
  1686.           dontBlock, dirtiedIndexPtr)
  1687.     Fsio_FileIOHandle        *handlePtr;    /* File to allocate block for.*/
  1688.     register Fsdm_FileDescriptor     *descPtr;    /* Pointer to the file desc. */
  1689.     register OfsBlockIndexInfo     *indexInfoPtr;     /* Index info structure. */
  1690.     int                newLastByte;    /* The new last byte in the 
  1691.                          * file. */
  1692.     int                curLastBlock;    /* The last block in the file 
  1693.                          * before started allocating. */
  1694.     int                dontBlock;    /* FSCACHE_DONT_BLOCK */
  1695.     Boolean            *dirtiedIndexPtr;/* TRUE if a new block was 
  1696.                           * allocated. */
  1697. {
  1698.     register    int         blockAddr;
  1699.     register    Ofs_Domain     *ofsPtr;
  1700.     unsigned char          *bitmapPtr;
  1701.     int                 newFragIndex;    /* {0, 1, 2, 3} */
  1702.     int                 blockNum;    /* Disk block that is 
  1703.                          * allocated. */
  1704.     int                 newFragOffset;    /* Offset in disk block where
  1705.                          * fragment begins. */
  1706.     ReturnStatus         status = SUCCESS;
  1707.  
  1708.     ofsPtr = indexInfoPtr->ofsPtr;
  1709.     blockAddr = *(indexInfoPtr->blockAddrPtr);
  1710.     if (blockAddr == 0 && handlePtr->hdr.fileID.minor != 2) {
  1711.     /*
  1712.      * The zero'th block belongs to the root directory which is
  1713.      * created by the makeFilesystem program.
  1714.      */
  1715.     printf("AllocateBlock: non-root file <%d,%d> with block 0\n",
  1716.             handlePtr->hdr.fileID.major, handlePtr->hdr.fileID.minor);
  1717.     return(FAILURE);
  1718.     }
  1719.  
  1720.     if (indexInfoPtr->blockNum >= FSDM_NUM_DIRECT_BLOCKS ||
  1721.     indexInfoPtr->blockNum < curLastBlock) {
  1722.     newFragIndex = LAST_FRAG;
  1723.     } else {
  1724.     newFragIndex = 
  1725.      (unsigned int) (newLastByte & FS_BLOCK_OFFSET_MASK) / FS_FRAGMENT_SIZE;
  1726.     }
  1727.  
  1728.     if (descPtr->lastByte == -1 || indexInfoPtr->blockNum != curLastBlock) {
  1729.     /*
  1730.      * Empty file or we are allocating a block that is before the
  1731.      * last block in the file.
  1732.      */
  1733.     if (newFragIndex < LAST_FRAG) {
  1734.         /*
  1735.          * Fragment the last block.
  1736.          */
  1737.         OfsFragFind(handlePtr->hdr.fileID.minor, ofsPtr,
  1738.             newFragIndex + 1, -1, -1, -1,
  1739.             &blockNum, &newFragOffset);
  1740.         if (blockNum != -1) {
  1741.         *(indexInfoPtr->blockAddrPtr) = 
  1742.                 blockNum * FS_FRAGMENTS_PER_BLOCK + newFragOffset;
  1743.         *dirtiedIndexPtr = TRUE;
  1744.         descPtr->numKbytes += newFragIndex + 1;
  1745.         } else {
  1746.         printf("AllocateBlock: OfsFragFind failed: no space on %s.\n",
  1747.                ofsPtr->domainPtr->domainPrefix); /* DEBUG */
  1748.         status = FS_NO_DISK_SPACE;
  1749.         }
  1750.     } else {
  1751.         /*
  1752.          * Allocate a full block if one isn't there already.
  1753.          */
  1754.         if (blockAddr == FSDM_NIL_INDEX) {
  1755.         OfsBlockFind(handlePtr->hdr.fileID.minor, ofsPtr,
  1756.                 indexInfoPtr->lastDiskBlock, 
  1757.                 TRUE, &blockNum, &bitmapPtr);
  1758.         if (blockNum == -1) {
  1759.         printf("AllocateBlock: OfsBlockFind failed: no space on %s.\n",
  1760.                ofsPtr->domainPtr->domainPrefix); /* DEBUG */
  1761.             status = FS_NO_DISK_SPACE;
  1762.         } else if (blockNum == 0 && handlePtr->hdr.fileID.minor != 2) {
  1763.             /*
  1764.              * The zero'th block belongs to the root directory which is
  1765.              * created by the makeFilesystem program.
  1766.              */
  1767.             printf("AllocateBlock: non-root file <%d,%d> wants block 0\n",
  1768.                 handlePtr->hdr.fileID.major,
  1769.                 handlePtr->hdr.fileID.minor);
  1770.             status = FAILURE;
  1771.         } else {
  1772.             *(indexInfoPtr->blockAddrPtr) = 
  1773.                         blockNum * FS_FRAGMENTS_PER_BLOCK;
  1774.             descPtr->numKbytes += FS_FRAGMENTS_PER_BLOCK;
  1775.             *dirtiedIndexPtr = TRUE;
  1776.         }
  1777.         }
  1778.     }
  1779.     } else {
  1780.     /*
  1781.      * Are allocating on top of the last block so make sure that the 
  1782.      * last fragment is large enough.
  1783.      */   
  1784.     status = UpgradeFragment(ofsPtr, handlePtr, indexInfoPtr, 
  1785.                  curLastBlock, newFragIndex, TRUE,
  1786.                  dontBlock, dirtiedIndexPtr);
  1787.     }
  1788.     return(status);
  1789. }
  1790.  
  1791.  
  1792. /*
  1793.  *----------------------------------------------------------------------
  1794.  *
  1795.  * FragToBlock --
  1796.  *
  1797.  *    Upgrade the given fragment to a block.
  1798.  *
  1799.  * Results:
  1800.  *    SUCCESS, FS_NO_DISK_SPACE, FS_WOULD_BLOCK.
  1801.  *
  1802.  * Side effects:
  1803.  *    The size in the file descriptor is updated so that it is on a block
  1804.  *    boundary.
  1805.  *
  1806.  *----------------------------------------------------------------------
  1807.  */
  1808. static ReturnStatus
  1809. FragToBlock(ofsPtr, handlePtr, blockNum, dontBlock)
  1810.     Ofs_Domain            *ofsPtr;
  1811.     register Fsio_FileIOHandle    *handlePtr;
  1812.     int                blockNum;
  1813.     int                dontBlock;    /* FSCACHE_DONT_BLOCK */
  1814. {
  1815.     register Fsdm_FileDescriptor    *descPtr;
  1816.     OfsBlockIndexInfo        indexInfo;
  1817.     ReturnStatus        status;
  1818.     Boolean            dirtiedIndex;
  1819.  
  1820.     /*
  1821.      * Set up the indexing structure.
  1822.      */
  1823.     descPtr = handlePtr->descPtr;
  1824.     if (blockNum == 0) {
  1825.     /*
  1826.      * This is the first block of the file so there is no previous
  1827.      * block.
  1828.      */
  1829.     status = OfsGetFirstIndex(ofsPtr, handlePtr, blockNum, &indexInfo,
  1830.                  OFS_ALLOC_INDIRECT_BLOCKS);
  1831.     if (status != SUCCESS) {
  1832.         return(status);
  1833.     }
  1834.     } else {
  1835.     /*
  1836.      * This is not the first block in the file, so determine the
  1837.      * previous block and then go to the first block.
  1838.      */
  1839.     status = OfsGetFirstIndex(ofsPtr, handlePtr, blockNum - 1, &indexInfo,
  1840.                  OFS_ALLOC_INDIRECT_BLOCKS);
  1841.     if (status != SUCCESS) {
  1842.         return(status);
  1843.     }
  1844.     status = OfsGetNextIndex(handlePtr, &indexInfo, FALSE);
  1845.     if (status != SUCCESS) {
  1846.         OfsEndIndex(handlePtr, &indexInfo, FALSE);
  1847.         return(status);
  1848.     }
  1849.     }
  1850.  
  1851.     /*
  1852.      * Now upgrade to a full block.
  1853.      */
  1854.  
  1855.     status = UpgradeFragment(ofsPtr, handlePtr, &indexInfo, blockNum, LAST_FRAG,
  1856.                  FALSE, dontBlock, &dirtiedIndex);
  1857.     if (status == SUCCESS) {
  1858.     descPtr->lastByte = blockNum * FS_BLOCK_SIZE + FS_BLOCK_SIZE - 1;
  1859.     descPtr->descModifyTime = Fsutil_TimeInSeconds();
  1860.     descPtr->flags |= FSDM_FD_SIZE_DIRTY;
  1861.     }
  1862.     OfsEndIndex(handlePtr, &indexInfo, dirtiedIndex);
  1863.     return(status);
  1864. }
  1865.  
  1866.  
  1867.  
  1868. /*
  1869.  *----------------------------------------------------------------------
  1870.  *
  1871.  * Ofs_DomainInfo --
  1872.  *
  1873.  *    Return info about the given domain.
  1874.  *
  1875.  * Results:
  1876.  *    Error  if can't get to the domain.
  1877.  *
  1878.  * Side effects:
  1879.  *    The domain info struct is filled in.
  1880.  *
  1881.  *----------------------------------------------------------------------
  1882.  */
  1883. ReturnStatus
  1884. Ofs_DomainInfo(domainPtr, domainInfoPtr)
  1885.     Fsdm_Domain    *domainPtr;
  1886.     Fs_DomainInfo    *domainInfoPtr;
  1887. {
  1888.     Ofs_Domain    *ofsPtr = OFS_PTR_FROM_DOMAIN(domainPtr);
  1889.  
  1890.     domainInfoPtr->maxKbytes = 
  1891.             ofsPtr->headerPtr->dataBlocks * FS_FRAGMENTS_PER_BLOCK;
  1892.     domainInfoPtr->freeKbytes = ofsPtr->summaryInfoPtr->numFreeKbytes;
  1893.     domainInfoPtr->maxFileDesc = ofsPtr->headerPtr->numFileDesc;
  1894.     domainInfoPtr->freeFileDesc = ofsPtr->summaryInfoPtr->numFreeFileDesc;
  1895.     domainInfoPtr->blockSize = FS_BLOCK_SIZE;
  1896.     domainInfoPtr->optSize = FS_BLOCK_SIZE;
  1897.  
  1898.     return(SUCCESS);
  1899. }
  1900.  
  1901.  
  1902.  
  1903. /*
  1904.  *----------------------------------------------------------------------
  1905.  *
  1906.  * Ofs_ReallocBlock --
  1907.  *
  1908.  *    Allocate a new block on disk to replace the given block.  This is
  1909.  *    intended to be used by the cache when it can't write out a block
  1910.  *    because of a disk error.
  1911.  *
  1912.  * Results:
  1913.  *     None
  1914.  *
  1915.  * Side effects:
  1916.  *    The descriptor or indirect blocks are modified to point to the newly
  1917.  *    allocated block.
  1918.  *
  1919.  *----------------------------------------------------------------------
  1920.  */
  1921. /*ARGSUSED*/
  1922. void
  1923. Ofs_ReallocBlock(data, callInfoPtr)
  1924.     ClientData        data;            /* Block to move */
  1925.     Proc_CallInfo    *callInfoPtr;        /* Not used. */
  1926. {
  1927.     Fscache_Block     *blockPtr = (Fscache_Block *) data;
  1928.     Fscache_FileInfo    *cacheInfoPtr = blockPtr->cacheInfoPtr;
  1929.     Fsio_FileIOHandle    *handlePtr = (Fsio_FileIOHandle *) cacheInfoPtr->hdrPtr;
  1930.     int            virtBlockNum, physBlockNum;
  1931.     OfsBlockIndexInfo    indexInfo;
  1932.     Fsdm_Domain        *domainPtr;
  1933.     int            newBlockNum = -1;
  1934.     Boolean        dirtiedIndex = FALSE;
  1935.     Boolean        setupIndex = FALSE;
  1936.     unsigned char    *bitmapPtr;
  1937.     ReturnStatus    status;
  1938.     Fsdm_FileDescriptor    *descPtr;
  1939.     Ofs_Domain        *ofsPtr;
  1940.  
  1941.     virtBlockNum = blockPtr->blockNum;
  1942.     physBlockNum = blockPtr->diskBlock;
  1943.     if (handlePtr->hdr.fileID.minor == 0) {
  1944.     /*
  1945.      * This is a descriptor block.
  1946.      */
  1947.     printf(
  1948.         "OfsBlockRealloc: Bad descriptor block.  Domain=%d block=%d\n",
  1949.           handlePtr->hdr.fileID.major, physBlockNum);
  1950.     goto error1;
  1951.     }
  1952.  
  1953.     domainPtr = Fsdm_DomainFetch(handlePtr->hdr.fileID.major, FALSE);
  1954.     if (domainPtr == (Fsdm_Domain *)NIL) {
  1955.     goto error;
  1956.  
  1957.     }
  1958.     ofsPtr = OFS_PTR_FROM_DOMAIN(domainPtr);
  1959.     Fsutil_HandleLock((Fs_HandleHeader *)handlePtr);
  1960.     descPtr = handlePtr->descPtr;
  1961.     if (virtBlockNum >= 0) {
  1962.     int        bytesInBlock;
  1963.     /*
  1964.      * A normal data block.
  1965.      */
  1966.     status = OfsGetFirstIndex(ofsPtr, handlePtr, virtBlockNum, &indexInfo, 0);
  1967.     if (status != SUCCESS) {
  1968.         printf( 
  1969.            "OfsBlockRealloc: Setup index (1) failed status <%x>\n", status);
  1970.         goto error;
  1971.     }
  1972.     setupIndex = TRUE;
  1973.     if (*indexInfo.blockAddrPtr != physBlockNum) {
  1974.         panic("OfsBlockRealloc: Bad physical block num.\n");
  1975.     }
  1976.     bytesInBlock = descPtr->lastByte - virtBlockNum * FS_BLOCK_SIZE + 1;
  1977.     if (bytesInBlock > FS_FRAGMENT_SIZE * (FS_FRAGMENTS_PER_BLOCK - 1) ||
  1978.         virtBlockNum >= FSDM_NUM_DIRECT_BLOCKS) {
  1979.         /* 
  1980.          * Have a full block.
  1981.          */
  1982.         OfsBlockFind(handlePtr->hdr.fileID.minor, ofsPtr,
  1983.             physBlockNum / FS_FRAGMENTS_PER_BLOCK, TRUE,
  1984.             &newBlockNum, &bitmapPtr);
  1985.         if (newBlockNum == -1) {
  1986.         printf( "FsdmBlockRealloc: No disk space (1)\n");
  1987.         goto error;
  1988.         }
  1989.         newBlockNum *= FS_FRAGMENTS_PER_BLOCK;
  1990.         *indexInfo.blockAddrPtr = newBlockNum;
  1991.         dirtiedIndex = TRUE;
  1992.         descPtr->flags |= FSDM_FD_INDEX_DIRTY;
  1993.         PutInBadBlockFile(handlePtr, ofsPtr, physBlockNum);
  1994.     } else {
  1995.         int    newFragOffset;
  1996.         int    numFrags;
  1997.         /*
  1998.          * Have a fragment.
  1999.          */
  2000.         numFrags = (bytesInBlock - 1) / FS_FRAGMENT_SIZE + 1;
  2001.         OfsFragFind(handlePtr->hdr.fileID.minor, ofsPtr, numFrags,
  2002.             -1, -1, -1, &newBlockNum, &newFragOffset);
  2003.         if (newBlockNum == -1) {
  2004.         printf( "FsdmBlockRealloc: No disk space (2)\n");
  2005.         goto error;
  2006.         }
  2007.         newBlockNum = newBlockNum * FS_FRAGMENTS_PER_BLOCK + newFragOffset;
  2008.         *indexInfo.blockAddrPtr = newBlockNum;
  2009.         dirtiedIndex = TRUE;
  2010.         descPtr->flags |= FSDM_FD_INDEX_DIRTY;
  2011.         if (OnlyFrag(ofsPtr, numFrags,
  2012.                physBlockNum / FS_FRAGMENTS_PER_BLOCK,
  2013.                physBlockNum & FRAG_OFFSET_MASK)) {
  2014.         PutInBadBlockFile(handlePtr, ofsPtr,
  2015.                   physBlockNum & ~FRAG_OFFSET_MASK);
  2016.         } else {
  2017.         /*
  2018.          * The fragment is in a block with other valid fragments.
  2019.          * We do nothing and just leave the fragment allocated
  2020.          * in the bitmap but unreferenced by any file.
  2021.          * This means checkFS should verify that an unreferenced
  2022.          * fragment is readable before marking it free.
  2023.          */
  2024.         printf( "Leaving bad frag #%d unreferenced\n",
  2025.                 physBlockNum);
  2026.         }
  2027.     }
  2028.     } else {
  2029.     Fscache_Block    *blockPtr = (Fscache_Block *)NIL;
  2030.     int        *blockAddrPtr;
  2031.  
  2032.     physBlockNum = -physBlockNum;
  2033.     if (virtBlockNum == -1) {
  2034.         /*
  2035.          * This is the first indirect block.
  2036.          */
  2037.         blockAddrPtr = &descPtr->indirect[0];
  2038.     } else if (virtBlockNum == -2) {
  2039.         /*
  2040.          * Second indirect block.
  2041.          */
  2042.         blockAddrPtr = &descPtr->indirect[1];
  2043.     } else if (descPtr->indirect[1] == FSDM_NIL_INDEX) {
  2044.         panic("OfsBlockRealloc: Can't find indirect block\n");
  2045.         blockAddrPtr = (int *) NIL;
  2046.     } else {
  2047.         Boolean    found;
  2048.         /*
  2049.          * Read in the doubly indirect block  so that we can get to the
  2050.          * indirect block that we want.
  2051.          */
  2052.         fs_Stats.blockCache.indBlockAccesses++;
  2053.         Fscache_FetchBlock(&handlePtr->cacheInfo, -2,
  2054.             FSCACHE_IND_BLOCK, &blockPtr, &found);
  2055.         if (!found) {
  2056.         status = OfsDeviceBlockIO(ofsPtr, FS_READ,
  2057.                descPtr->indirect[1], FS_FRAGMENTS_PER_BLOCK, 
  2058.                blockPtr->blockAddr);
  2059.         if (status != SUCCESS) {
  2060.             printf( 
  2061.     "OfsBlockRealloc: Could not read doubly indirect block, status <%x>\n", 
  2062.             status);
  2063.             Fscache_UnlockBlock(blockPtr, 0, 0, 0, FSCACHE_DELETE_BLOCK);
  2064.             goto error;
  2065.         } else {
  2066.             fs_Stats.gen.physBytesRead += FS_BLOCK_SIZE;
  2067.         }
  2068.         } else {
  2069.         fs_Stats.blockCache.indBlockHits++;
  2070.         }
  2071.         blockAddrPtr = (int *)blockPtr->blockAddr + (-virtBlockNum - 3);
  2072.     }
  2073.     if (*blockAddrPtr != physBlockNum) {
  2074.         panic("OfsBlockRealloc: Bad phys addr for indirect block (2)\n");
  2075.     }
  2076.     /*
  2077.      * Allocate a new indirect block.
  2078.      */
  2079.     OfsBlockFind(handlePtr->hdr.fileID.minor, ofsPtr, -1, TRUE, 
  2080.             &newBlockNum, &bitmapPtr);
  2081.     if (newBlockNum == -1) {
  2082.         printf( "FsdmBlockRealloc: No disk space (3)\n");
  2083.         goto error;
  2084.     }
  2085.     newBlockNum = (newBlockNum + ofsPtr->headerPtr->dataOffset) * 
  2086.             FS_FRAGMENTS_PER_BLOCK;
  2087.     *blockAddrPtr = newBlockNum;
  2088.     if (blockPtr == (Fscache_Block *)NIL) {
  2089.         descPtr->flags |= FSDM_FD_INDEX_DIRTY;
  2090.     } else {
  2091.         Fscache_UnlockBlock(blockPtr, (unsigned int)Fsutil_TimeInSeconds(), 
  2092.                    -(descPtr->indirect[1]), FS_BLOCK_SIZE, 0);
  2093.     }
  2094.     PutInBadBlockFile(handlePtr, ofsPtr,
  2095.               physBlockNum - FS_FRAGMENTS_PER_BLOCK * 
  2096.                      ofsPtr->headerPtr->dataOffset);
  2097.     newBlockNum = -newBlockNum;
  2098.     }
  2099.  
  2100. error:
  2101.  
  2102.     if (setupIndex) {
  2103.     OfsEndIndex(handlePtr, &indexInfo, dirtiedIndex);
  2104.     }
  2105.     Fsdm_DomainRelease(handlePtr->hdr.fileID.major);
  2106.     Fsutil_HandleUnlock((Fs_HandleHeader *)handlePtr);
  2107. error1:
  2108.     FscacheFinishRealloc(blockPtr, newBlockNum);
  2109.     return;
  2110. }
  2111.  
  2112.  
  2113. /*
  2114.  *----------------------------------------------------------------------
  2115.  *
  2116.  * PutInBadBlockFile --
  2117.  *
  2118.  *    Put the given physical block into the bad block file.
  2119.  *
  2120.  * Results:
  2121.  *    None.
  2122.  *
  2123.  * Side effects:
  2124.  *    Block appended to the bad block file.
  2125.  *
  2126.  *----------------------------------------------------------------------
  2127.  */
  2128. static void
  2129. PutInBadBlockFile(handlePtr, ofsPtr, blockNum)
  2130.     Fsio_FileIOHandle    *handlePtr;    /* File which owned bad block. */
  2131.     Ofs_Domain    *ofsPtr;        /* Pointer to domain. */
  2132.     int        blockNum;    /* Block number to put in bad block file. */
  2133. {
  2134.     Fs_FileID        fileID;
  2135.     Fsio_FileIOHandle    *badBlockHandlePtr;
  2136.     Fsdm_FileDescriptor    *descPtr;
  2137.     OfsBlockIndexInfo    indexInfo;
  2138.     ReturnStatus    status;
  2139.     int            lastBlock;
  2140.  
  2141.     fileID.serverID = rpc_SpriteID;
  2142.     fileID.type = FSIO_LCL_FILE_STREAM;
  2143.     fileID.major = handlePtr->hdr.fileID.major;
  2144.     fileID.minor = OFS_BAD_BLOCK_FILE_NUMBER;
  2145.     badBlockHandlePtr = (Fsio_FileIOHandle *)Fsutil_HandleFetch(&fileID);
  2146.     if (badBlockHandlePtr == (Fsio_FileIOHandle *)NIL) {
  2147.     /*
  2148.      * Have to make a new handle since we don't have one for this domain
  2149.      * in memory.
  2150.      */
  2151.     status = Fsio_LocalFileHandleInit(&fileID, "BadBlockFile",
  2152.             (Fsdm_FileDescriptor *) NIL, FALSE, 
  2153.             &badBlockHandlePtr);
  2154.     if (status != SUCCESS) {
  2155.         printf("PutInBadBlockFile: error %x reading descriptor\n", status);
  2156.         return;
  2157.     }
  2158.     }
  2159.     descPtr = badBlockHandlePtr->descPtr;
  2160.     if (descPtr->lastByte != -1) {
  2161.     lastBlock = descPtr->lastByte / FS_BLOCK_SIZE;
  2162.     } else {
  2163.     lastBlock = -1;
  2164.     }
  2165.     status = OfsGetFirstIndex(ofsPtr, handlePtr, lastBlock + 1, &indexInfo,
  2166.                  OFS_ALLOC_INDIRECT_BLOCKS);
  2167.     if (status != SUCCESS) {
  2168.     printf( "PutInBadBlockFile: Could not fetch index\n");
  2169.     } else {
  2170.     *indexInfo.blockAddrPtr = blockNum;
  2171.     descPtr->lastByte += FS_BLOCK_SIZE;
  2172.     descPtr->flags |= (FSDM_FD_INDEX_DIRTY|FSDM_FD_SIZE_DIRTY);
  2173.     descPtr->numKbytes += FS_FRAGMENTS_PER_BLOCK;
  2174.     OfsEndIndex(handlePtr, &indexInfo, TRUE);
  2175.     }
  2176.  
  2177.     Fsutil_HandleUnlock((Fs_HandleHeader *)badBlockHandlePtr);
  2178. }
  2179.